// Created by 11372 on 2021/12/14 15:03
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/**
 * 执行用时：200 ms, 在所有 C++ 提交中击败了66.67%的用户
 * 内存消耗：54.9 MB, 在所有 C++ 提交中击败了48.86%的用户
 */
class Solution {
public:
    int scheduleCourse(vector<vector<int>> &courses) {
        sort(courses.begin(), courses.end(), [](vector<int> &a, vector<int> &b) {
            return a[1] < b[1];
        });

        priority_queue<int> heap;
        int tot = 0;  // 选出的课程用时
        for (auto &c : courses) {
            tot += c[0];
            heap.push(c[0]);
            if (tot > c[1]) {
                tot -= heap.top();
                heap.pop();
            }
        }
        return heap.size();
    }
};

int main() {

    vector<vector<int>> courses = {
            {100,  200},
            {200,  1300},
            {1000, 1250},
            {2000, 3200},
    };
    cout << Solution().scheduleCourse(courses) << endl;  // 3

    return 0;
}
